package com.bwt.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class QuickSort {
    public static void main(String[] args) {
        //int[] arr = {-9, 78, 0, 23, -567, 70};
        //int[] arr = {1,2,1,5,0,1};

        int[] arr = new int[8000000];
        for(int i = 0;i < 80000;i++){
            arr[i] = (int)(Math.random() * 80000);	//自动生成[0,80000)之间的随机数
        }

        //快排时间复杂度 O(logn)
        Date data = new Date();
        SimpleDateFormat simt = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String dateS = simt.format(data);
        System.out.println("排序前的时间是:" + dateS);

        quickSort(arr, 0, arr.length-1);

        //排序后的时间:
        Date data2 = new Date();
        SimpleDateFormat simt2 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String dateS2 = simt2.format(data2);
        System.out.println("排序后的时间是:" + dateS2);


        /*排序前的时间是:2022-07-27 09:22:42
         排序后的时间是:2022-07-27 09:22:44*/

        //System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr, int left, int right) {
        int l = left; //左下标
        int r = right; //右下标
        // pivot 是中轴值
        int pivot = arr[(left + right) / 2];
        int temp; //临时变量 交换时使用
        //while循环的目的 是让比pivot的值小的放到左边
        //比pivot 大的放到右边
        while (l < r) {
            //在privot左边一直找, 找到大于等于pivot的值才会不进入循环(退出)
            while (arr[l] < pivot) {
                l += 1;
            }
            //在privot右边一直找, 找到小于等于pivot的值才会不进入循环(退出)
            while (arr[r] > pivot) {
                r -= 1;
            }
            //如果l >= r 说明pivot左右两边的值 已经左边全是小于等于pivot的值,右边全是大于等于pivot的值
            if (l >= r) {
                break;
            }
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            //如果交换完了之后 发现arr[l] == pivot 那么让r-- 右边前移
            /**
             * int[] arr = {1,2,5,1,0,1};
             * 例 这个数组 arr[0] = 1  arr[5] = 5  加入pivot ==1
             * l = 0 r =5
             * 交换arr[l] 和arr[r]
             *
             * 交换过后有两种情况
             * 1. 交换的值与pivot相等 则后移和前移指针 继续循环
             * 2. 交换的值是pivot本身, 就是说前后指针都已经重合, 说明pivot 两边已经都是它大或者比它小的数 这时后移和前移指针 会导致l>r 所以不会继续循环, 进入递归条件
             */
            if (arr[l] == pivot) {
                r -= 1;
            }
            //如果交换完了之后 发现arr[r] == pivot 那么让l++ 左边后移
            if (arr[r] == pivot) {
                l += 1;
            }
        }
        //如果 l==r 说明左右两边指针已经重合, 两边已经没有比privot大或小的值, 所以各向前一步,然后递归
        if (l == r) {
            l += 1;
            r -= 1;
        }
        if (left < r) {
            quickSort(arr,left,r);
        }
        if (right > l) {
            quickSort(arr,l,right);
        }
    }
}
